package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-23
 */

/**
 * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
 *
 * nums[0] = 0
 * nums[1] = 1
 * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
 * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
 * 返回生成数组 nums 中的 最大 值。
 */
public class leetcode1646 {
    public int getMaximumGenerated(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
        int max = 1;
        int[] dp = new int[n+1]; dp[0]=0;dp[1]=1;
        for (int i = 1; i < n && 2*i+1<=n; i++) {
            dp[2*i] = dp[i];
            dp[2*i+1] = dp[i]+dp[i+1];
            max = Math.max(max, Math.max(dp[2*i],dp[2*i+1]));
        }
        return max;
    }
}
